# 最大公因数
# 求两个数的最大公因数

# 初等数论 辗转相除法

"""
Tip:
    辗转相除法
    两个整数的最大公约数等于其中较小数和两数相除余数的最大公约数。
    gcd(a, b) = gcd(b, a mod b)
"""


# 递推
def func1(a: int, b: int) -> int:
    if a == b:
        return a
    num = min(a, b)
    while a % num != 0 or b % num != 0:
        num -= 1
    return num


def func2(a: int, b: int) -> int:
    while b != 0:
        a, b = b, a % b
    return a


print(func1(12, 18))
print(func2(12, 18))
